package com.fr.lintcode;

import java.util.HashMap;
import java.util.Map;

/**
*作者：furong
*日期：2017年1月16日
*时间：上午11:13:07
*/
public class Q105 {
    class RandomListNode {
        int label;
        RandomListNode next, random;

        RandomListNode(int x) {
            this.label = x;
        }
    }

    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    public RandomListNode copyRandomList(RandomListNode head) {
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode c = head;
        while (c != null) {
            RandomListNode a = new RandomListNode(c.label);
            map.put(c, a);
            c = c.next;
        }
        c = head;
        while (c != null) {
            RandomListNode a = map.get(c);
            a.next = map.get(c.next);
            a.random = map.get(c.random);
            c = c.next;
        }
        return map.get(head);
    }
}
